Intersection of two array [Hash, Binary Search]

Time: O(M+N); Space: O(min(M,N)); easy

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [9,4]

Notes:

• Each element in the result must be unique.

• The result can be in any order.

1. Two pointers solution

class Solution1(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort(), nums2.sort()
        res = []

        it1, it2 = 0, 0
        while it1 < len(nums1) and it2 < len(nums2):
            if nums1[it1] < nums2[it2]:
                it1 += 1
            elif nums1[it1] > nums2[it2]:
                it2 += 1
            else:
                if not res or res[-1] != nums1[it1]:
                    res += nums1[it1],
                it1 += 1
                it2 += 1

        return res

s = Solution1()

nums1 = [1,2,2,1]
nums2 = [2,2]
assert s.intersection(nums1, nums2) == [2]

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
assert s.intersection(nums1, nums2) == [9,4] or [4,9]

2. Binary search solution

class Solution2(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        if len(nums1) > len(nums2):
            return self.intersection(nums2, nums1)

        def binary_search(compare, nums, left, right, target):
            while left < right:
                mid = left + (right - left) // 2
                if compare(nums[mid], target):
                    right = mid
                else:
                    left = mid + 1
            return left

        nums1.sort(), nums2.sort()

        res = []
        left = 0
        for i in nums1:
            left = binary_search(lambda x, y: x >= y, nums2, left, len(nums2), i)
            if left != len(nums2) and nums2[left] == i:
                res += i,
                left = binary_search(lambda x, y: x > y, nums2, left, len(nums2), i)

        return res

s = Solution2()

nums1 = [1,2,2,1]
nums2 = [2,2]
assert s.intersection(nums1, nums2) == [2]

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
assert s.intersection(nums1, nums2) == [9,4] or [4,9]

3. Using one set

class Solution3(object):
    """
    Time: O(M+N)
    Space: O(MIN(M,N))
    """
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        if len(nums1) > len(nums2):
            return self.intersection(nums2, nums1)

        lookup = set()
        for i in nums1:
            lookup.add(i)

        res = []
        for i in nums2:
            if i in lookup:
                res += i,
                lookup.discard(i)

        return res

s = Solution3()

nums1 = [1,2,2,1]
nums2 = [2,2]
assert s.intersection(nums1, nums2) == [2]

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
assert s.intersection(nums1, nums2) == [9,4] or [4,9]

4. Using two sets [O(M+N),O(M+N)]

Intuition

The naive approach would be to iterate along the first array nums1 and to check for each value if this value in nums2 or not. If yes - add the value to output. Such an approach would result in a pretty bad O(N×M) time complexity, where N and M are arrays’ lengths.

To solve the problem in linear time, let’s use the structure set, which provides in/contains operation in O(1) time in average case.

The idea is to convert both arrays into sets, and then iterate over the smallest set checking the presence of each element in the larger set. Time complexity of this approach is O(N + M) in the average case.

class Solution4(object):
    """
    Time: O(m+n), where n and m are arrays' lengths.
          O(n) time is used to convert nums1 into set,
          O(m) time is used to convert nums2,
          and contains/in operations are O(1) in the average case.
    Space: O(m+n) in the worst case when all elements in the arrays are different.
    """
    def set_intersection(self, set1, set2):
        return [x for x in set1 if x in set2]

    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        set1 = set(nums1)
        set2 = set(nums2)

        if len(set1) < len(set2):
            return self.set_intersection(set1, set2)
        else:
            return self.set_intersection(set2, set1)

s = Solution4()

nums1 = [1,2,2,1]
nums2 = [2,2]
assert s.intersection(nums1, nums2) == [2]

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
assert s.intersection(nums1, nums2) == [9,4] or [4,9]

5. Built-in Set Intersection [O(NxM), O(N+M]

Intuition

There are built-in intersection facilities, which provide O(N+M) time complexity in the average case and O(N×M) time complexity in the worst case.

class Solution5(object):
    """
    Time: O(n+m) in the average case and O(n×m) in the worst case when load factor is high enough.
    Space: O(n+m) in the worst case when all elements in the arrays are different.
    """
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        return list(set(nums1) & set(nums2))

s = Solution5()

nums1 = [1,2,2,1]
nums2 = [2,2]
assert s.intersection(nums1, nums2) == [2]

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
assert s.intersection(nums1, nums2) == [9,4] or [4,9]

See also:

https://leetcode.com/problems/intersection-of-two-arrays

https://www.lintcode.com/problem/intersection-of-two-arrays/description

Related problems:

https://leetcode.com/problems/intersection-of-two-arrays-ii/

https://leetcode.com/problems/intersection-of-three-sorted-arrays/